//
// Created by 2592345590 on 2022/5/11.
//

#include "GAnalysis.h"

/**
 * G1
E
E+T|T
T
T*F|F
F
i|(E)
markzero

 */
GAnalysis::GAnalysis() {
    cout << "语法分析" << endl << "开始输入文法（输入markzero停止输入）" << endl;
    string g;
    null='@';
    Terminator.push_back(null);
    int i;
    while (cout << "请输入非终结符，如 E：" && getline(cin, g) && g != "markzero") {
        noTerminator.push_back(g);
        noTerminatorChild.push_back(vector<string>());
        cout << "请输入" << g << "的全部推导式，以|分割，如 E-F|F ：";
        getline(cin, g);
        string temp;
        for (i = 0; i < g.length() || !temp.empty(); i++) {
            if (i >= g.length() || g[i] == '|') {
                noTerminatorChild[noTerminator.size() - 1].push_back(temp);
                AddWord(temp);//送去词法分析，存储终结符
                temp = "";
            } else if (i < g.length())
                temp += g[i];
        }
    }
    Print();
    RmLRecursion();
    first.resize(noTerminator.size());
    First();
    follow.resize(noTerminator.size());
    Follow();
    //有多少个推导式就有多少个select
    select.resize(noTerminator.size());
    Select();
}

void GAnalysis::Print() {
    cout << "当前文法:" << endl;
    int i, j;
    for (i = 0; i < noTerminator.size(); i++) {
        cout << noTerminator[i] << " ->";
        for (j = 0; j < noTerminatorChild[i].size(); j++) {
            if (!j)
                cout << noTerminatorChild[i][j];
            else
                cout << "|" << noTerminatorChild[i][j];
        }
        cout << endl;
    }
}

void GAnalysis::RmLRecursion() {
    cout << "开始消除左递归:" << endl;
    RmLDRecursion();
    RmLIRecursion();
    cout << "左递归消除完毕" << endl;
}

void GAnalysis::RmLDRecursion() {
    cout << "开始消除直接递归:" << endl;
    string newG;
    vector<string> newNoTerminator;
    vector<vector<string> > newNoTerminatorChild;
    int i, j;
    for (i = 0; i < noTerminator.size(); i++) {
        vector<string> is;//这个推导式有左递归 则记住非终结符后面的字符 E->ET|EF|D|G 记住T&F
        vector<string> isn;//没有的就全部记住 E->ET|EF|D|G 记住D&G
        for (j = 0; j < noTerminatorChild[i].size(); j++) {
            if (noTerminatorChild[i][j].find(noTerminator[i]) == 0) {//出现在首字符
                is.push_back(noTerminatorChild[i][j].substr(noTerminator[i].length()));//记住后面的字符
            } else {
                isn.push_back(noTerminatorChild[i][j]);
            }
        }
        if (!is.empty()) {//该非终结符含有左递归
            newG = noTerminator[i] + "'";
            //化为 E->DE'|GE'
            newNoTerminator.push_back(noTerminator[i]);
            newNoTerminatorChild.push_back(vector<string>());
            for (j = 0; j < isn.size(); j++) {
                newNoTerminatorChild[newNoTerminator.size() - 1].push_back(isn[j] + newG);
            }
            //E'->TE'|FE'|@
            newNoTerminator.push_back(newG);
            newNoTerminatorChild.push_back(vector<string>());
            for (j = 0; j < is.size(); j++) {
                newNoTerminatorChild[newNoTerminator.size() - 1].push_back(is[j] + newG);
            }
            newNoTerminatorChild[newNoTerminator.size() - 1].push_back(null);
        } else {//该非终结符没有左递归
            newNoTerminator.push_back(noTerminator[i]);
            newNoTerminatorChild.push_back(noTerminatorChild[i]);
        }
    }
    noTerminator = newNoTerminator;
    noTerminatorChild = newNoTerminatorChild;
    cout << "直接递归消除完毕" << endl;
    Print();
}

void GAnalysis::RmLIRecursion() {
    cout << "开始消除间接递归:" << endl;

    cout << "间接递归消除完毕" << endl;
}

void GAnalysis::First() {
    for (int i = 0; i < noTerminator.size(); i++)
        first[i] = GetFirst(i);//求该非终结符的first值
    PrintFirst();
}

/**
E
TE'
E'
+TE'|c
T
FT'
T'
*FT'|c
F
(E)|i
markzero

**/
vector<string> GAnalysis::GetFirst(int x) {
    if (!first[x].empty())
        return first[x];
    for (int i = 0; i < noTerminatorChild[x].size(); i++) {//遍历推导式
        //获取推导式第一个字符集 和 判断是不是非终结符 和 获取这个非终结符的下标
        bool flag = false;
        int pos = -1;
        string firstStr = GetStringFirst(noTerminatorChild[x][i], &flag, &pos);
        if(noTerminatorChild[x][i]==null)
            cout<<"here"<<firstStr<<" ";
        //判断推导式第一个字符是不是非终结符 不是就直接加入first（x）中，是就进入它的推导式
        if (flag) {
            AddFirst(x, GetFirst(pos));
        } else {
            vector<string> temp;
            temp.push_back(firstStr);
            AddFirst(x, temp);
        }
    }
    return first[x];
}

void GAnalysis::PrintFirst() {
    cout<<"First:"<<endl;
    for (int i = 0; i < noTerminator.size(); i++) {
        cout << "First(" << noTerminator[i] << ")={";
        for (int j = 0; j < first[i].size(); j++) {
            if (!j)
                cout << first[i][j];
            else
                cout << "," << first[i][j];
        }
        cout << "}" << endl;
    }
}

void GAnalysis::Follow() {
    follow[0].push_back(null);//规则1
    //A->aBc c!=null First(c)中除了null以外加入follow[B]
    for (int i = 0; i < noTerminator.size(); i++) {
        for (int j = 0; j < noTerminator.size(); j++) {
            for (int k = 0; k < noTerminatorChild[j].size(); k++) {
                int pos = (int) (noTerminatorChild[j][k].find(noTerminator[i]));
                if (pos != -1 && (pos == noTerminatorChild[j][k].length() - noTerminator[i].length() ||
                                  noTerminatorChild[j][k][pos + noTerminator[i].length()] != '\'')) {
                    bool flag = false;
                    int pint = 0;
                    string nextWord = GetStringFirst(noTerminatorChild[j][k].substr(pos + noTerminator[i].length()),
                                                     &flag, &pint);
                    int nextWordi = (int) (&*find(noTerminator.begin(), noTerminator.end(), nextWord) -
                                           &noTerminator[0]);
                    if (flag && nextWord != null) {//规则2
                        for (int l = 0; l < first[nextWordi].size(); l++) {
                            if (first[nextWordi][l] != null &&
                                find(follow[i].begin(), follow[i].end(), first[nextWordi][l]) == follow[i].end())
                                follow[i].push_back(first[nextWordi][l]);
                        }
                    }
                    if (nextWord.empty() || (flag && find(first[nextWordi].begin(), first[nextWordi].end(), null) !=
                                                     first[nextWordi].end())) {//规则3
                        for (int l = 0; l < follow[j].size(); l++) {
                            if (find(follow[i].begin(), follow[i].end(), follow[j][l]) == follow[i].end())
                                follow[i].push_back(follow[j][l]);
                        }
                    }
                    if (!flag && !nextWord.empty()) {
                        char a = noTerminatorChild[j][k][pos + 1];
                        string str;
                        str += a;
                        if (find(follow[i].begin(), follow[i].end(), str) == follow[i].end())
                            follow[i].push_back(str);
                    }
                }
            }
        }
    }
    PrintFollow();
}

string GAnalysis::GetStringFirst(string str, bool *pBoolean, int *pInt) {
    string result;//记录该非终结符
    //判断有无非终结符 记录最先出现的非终结符的位置
    for (int i = 0; i < noTerminator.size(); i++) {
        if ((int) str.find(noTerminator[i]) == 0) {//记录非终结符
            result = noTerminator[i];
            *pBoolean = true;
            *pInt = i;
        }
    }
    //如果result存在，说明首字符是非终结符 返回
    if (!result.empty())
        return result;
    //如果没有 返回第一个终结符
    else {
        for (int i = 0; i < Terminator.size(); ++i) {
            if(str.find(Terminator[i])==0){
                result=Terminator[i];
            }
        }
        return result;
    }

}

void GAnalysis::AddFirst(int x, vector<string> str) {
    //判断first[x]中是否已经有了str[i] 有就不加 没有就加
    for (int i = 0; i < str.size(); i++)
        if (find(first[x].begin(), first[x].end(), str[i]) == first[x].end())
            first[x].push_back(str[i]);
}

void GAnalysis::PrintFollow() {
    cout<<"Follow:"<< endl;
    for (int i = 0; i < noTerminator.size(); i++) {
        cout << "Follow(" << noTerminator[i] << ")={";
        for (int j = 0; j < follow[i].size(); j++) {
            if (!j)
                cout << follow[i][j];
            else
                cout << "," << follow[i][j];
        }
        cout << "}" << endl;
    }
}

void GAnalysis::Select() {
    for (int i = 0; i < noTerminator.size(); ++i) {
        select[i].resize(noTerminatorChild[i].size());
        for (int j = 0; j < noTerminatorChild[i].size(); ++j) {
            if(noTerminatorChild[i][j]==null)
                select[i][j]=follow[i];
            else{
                //first(noTerminatorChild[i])
                //如果首字符是非终结符 则等于first(非终结符)
                bool flag=false;int pint;
                string firstC=GetStringFirst(noTerminatorChild[i][j],&flag,&pint);
                if(flag){
                    select[i][j]=first[(int) (&*find(noTerminator.begin(), noTerminator.end(), firstC) -
                                              &noTerminator[0])];
                }
                //不是就等于第一个字符
                else{
                    select[i][j].push_back(firstC);
                }
            }
        }
    }
    PrintSelect();
}

void GAnalysis::PrintSelect() {
    cout<<"Select:"<<endl;
    for (int i = 0; i < noTerminator.size(); ++i) {
        for (int j = 0; j < noTerminatorChild[i].size(); ++j) {
            cout<<noTerminator[i]<<"->";
            for (int k = 0; k < noTerminatorChild[i][j].size(); ++k) {
                cout<<noTerminatorChild[i][j][k];
            }
            cout<<"={";
            for (int k = 0; k < select[i][j].size(); ++k) {
                if (!k)
                    cout<<select[i][j][k];
                else
                    cout<<","<<select[i][j][k];
            }
            cout<<"}"<<" ";
        }
        cout<<endl;
    }
}

bool GAnalysis::Analysis(string input) {
    //初始化分析栈
    stack<string> S;
    S.push(noTerminator[0]);
    int count=1,inputi=0;
    string str="phase";
    printf("%5s",str.c_str());
    str="stack";
    printf("%20s",str.c_str());
    str="input";
    printf("%20s",str.c_str());
    str="pFormula";
    printf("%20s\n",str.c_str());
    while(!S.empty()){
        printf("%5d",count);
        PrintStack(S);
        printf("%20s",input.substr(inputi).c_str());
        string nextword;int nextwordL=0;
        if(inputi<input.length())
            nextword= GetNextWord(input.substr(inputi),&nextwordL);//输入串下个单词
        string sTop=S.top();
        S.pop();
        int noTi=(int)(&*find(noTerminator.begin(), noTerminator.end(), sTop)-&noTerminator[0]);//看看是不是某个非终结符
        if(sTop==nextword){
            inputi+=nextwordL;
        }else if(noTi>=0&& noTi<noTerminator.size()){//非终结符
            bool flag=false;
            //寻找所用产生式
            for (int i = 0; i < select[noTi].size(); ++i) {
                if(find(select[noTi][i].begin(), select[noTi][i].end(), nextword)!=select[noTi][i].end()||(nextword.empty()&&find(select[noTi][i].begin(), select[noTi][i].end(), null)!=select[noTi][i].end())){//找到了这个产生式
                    flag=true;
                    string produceFormula=noTerminatorChild[noTi][i];
                    //打印所用产生式
                    printf("%20s",(noTerminator[noTi]+"->"+produceFormula).c_str());
                    if(produceFormula==null){
                        break;
                    }
                    //把该产生式从右到左放入栈中
                    vector<string> temp;
                    for(int j=0;j<produceFormula.length();){
                        bool a;int b;
                        temp.push_back(GetStringFirst(produceFormula.substr(j),&a,&b));
                        j+=(int)temp[temp.size()-1].length();
                    }
                    for(int j=(int)temp.size()-1;j>=0;j--){
                        S.push(temp[j]);
                    }
                    break;
                }
            }
            if(!flag){
                cout<<"未找到产生式"<<endl;
                return false;
            }
        }else{
            cout<<"出错了"<<endl;
            return false;
        }
        count++;
        cout<<endl;
    }
    if(S.empty()&&inputi==input.length()){
        printf("%5d",count);
        PrintStack(S);
        printf("%20s",input.substr(inputi).c_str());
        printf("%20s\n","accept");
        return true;
    }
    return false;
}

void GAnalysis::PrintStack(stack<string> data) {
    string str;
    while(!data.empty()){
        str=data.top()+str;
        data.pop();
    }
    printf("%20s",str.c_str());
}

void GAnalysis::AddWord(string str) {
    //先分词 空格分词 符号分词 大小写分词
    string temp;
    for(int i=0;i<str.length();){
        if(str[i]>='a'&&str[i]<='z'){
            temp+=str[i];
            i++;
        }else if(str[i]>='A'&&str[i]<='Z'){
            if(!temp.empty()&&find(Terminator.begin(), Terminator.end(), temp)==Terminator.end()&&find(noTerminator.begin(), noTerminator.end(), temp)==noTerminator.end())//如果终结符表中和非终结符表中没有
                Terminator.push_back(temp);
            temp="";
            i++;
        }else if((str[i]>='A'&&str[i]<='Z')&&str[i+1]=='\''){
            if(!temp.empty()&&find(Terminator.begin(), Terminator.end(), temp)==Terminator.end()&&find(noTerminator.begin(), noTerminator.end(), temp)==noTerminator.end())//如果终结符表中和非终结符表中没有
                Terminator.push_back(temp);
            temp="";
            i+=2;
        }else{//符号
            if(!temp.empty()&&find(Terminator.begin(), Terminator.end(), temp)==Terminator.end()&&find(noTerminator.begin(), noTerminator.end(), temp)==noTerminator.end())//如果终结符表中和非终结符表中没有
                Terminator.push_back(temp);
            temp="";
            temp+=str[i];
            if(!temp.empty()&&find(Terminator.begin(), Terminator.end(), temp)==Terminator.end()&&find(noTerminator.begin(), noTerminator.end(), temp)==noTerminator.end())//如果终结符表中和非终结符表中没有
                Terminator.push_back(temp);
            temp="";
            i++;
        }
    }
    if(!temp.empty()&&find(Terminator.begin(), Terminator.end(), temp)==Terminator.end()&&find(noTerminator.begin(), noTerminator.end(), temp)==noTerminator.end())//如果终结符表中和非终结符表中没有
        Terminator.push_back(temp);
}

string GAnalysis::GetNextWord(string input,int *len) {
    //先找终结符
    for (int i = 0; i < Terminator.size(); ++i) {
        if(input.find(Terminator[i])==0){
            *len=(int)Terminator[i].length();
            return Terminator[i];
        }
    }
    //符号|空格分割 即找变量
    string result;
    for(int i=0;i<input.length();i++){
        if((input[i]>='a'&&input[i]<='z')||(input[i]>='0'&&input[i]<='9')){
            result+=input[i];
        }else{
            if(!result.empty()){
                *len=(int)result.length();
                result="id";
                return result;
            }
            result+=input[i];
            *len=(int)result.length();
            return result;
        }
    }
    if(!result.empty())
    {
        *len=(int)result.length();
        result="id";
    }
    return result;
}